/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ads.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Set;

/**
 *
 * @author framet-lap
 */
//Graph imported from the crazy shizzle ebook "Algorithmen und Datenstrukturen"
public class Graph {

    // Kante
    static class Edge {

        Node dest; // Zielknoten
        Integer cost; // Kantengewicht

        public Edge(Node n, Integer c) {
            dest = n;
            cost = c;
        }

        public Node getDestNode() {
            return dest;
        }

        public int getCost() {
            return cost;
        }

        public Integer getCostI() {
            return cost;
        }
    }
// Knoten

    public static class Node {

        String label; // Knotenbezeichner
        int costToStartNode;
        Node comesFrom;
// Adjazenzliste
        ArrayList<Edge> adjList = new ArrayList<Edge>();

        public Node(String s) {
            label = s;
        }

        public String getLabel() {
            return label;
        }

        public void addEdge(Edge e) {
            adjList.add(e);
        }

        public void removeEdge(Edge e) {
            adjList.remove(e);
        }

        public Iterator<Edge> getEdges() {
            return adjList.iterator();
        }

        public Edge getEdgeTo(Node n) {
            for (Edge e : adjList) {
                if (e.dest.equals(n)) {
                    return e;
                }
            }
            return null;
        }

        public class BFSData {

            private int level;

            public BFSData(int level) {
                this.level = level;
            }

            /**
             * @return the level
             */
            public int getLevel() {
                return level;
            }

            /**
             * @param level the level to set
             */
            public void setLevel(int level) {
                this.level = level;
            }
        }

        private class BFSSearchData {

            private Node node;
            private int workingLevel;

            private BFSSearchData(Node node, int workingLevel) {
                this.node = node;
                this.workingLevel = workingLevel;
            }

            /**
             * @return the node
             */
            public Node getNode() {
                return node;
            }

            /**
             * @param node the node to set
             */
            public void setNode(Node node) {
                this.node = node;
            }

            /**
             * @return the workingLevel
             */
            public int getWorkingLevel() {
                return workingLevel;
            }

            /**
             * @param workingLevel the workingLevel to set
             */
            public void setWorkingLevel(int workingLevel) {
                this.workingLevel = workingLevel;
            }
        }

        public HashMap<Node, BFSData> BFS() {
            HashMap<Node, BFSData> result = new HashMap<Node, BFSData>();
            LinkedList<BFSSearchData> concurrentKeyList = new LinkedList<>();
            concurrentKeyList.add(new BFSSearchData(this, 0));

            return BFS(result, concurrentKeyList);
        }

        private HashMap<Node, BFSData> BFS(HashMap<Node, BFSData> map, LinkedList<BFSSearchData> concurrentKeyList) {
            BFSSearchData nextNode;
            do {
                nextNode = concurrentKeyList.peek();

                if (nextNode != null) {
                    BFSData existingData = map.get(nextNode.getNode());
                    if (existingData == null) {
                        map.put(nextNode.getNode(), new BFSData(nextNode.getWorkingLevel()));
                    } else if (existingData.getLevel() > nextNode.getWorkingLevel()) {
                        existingData.setLevel(nextNode.getWorkingLevel());
                    }
                    addEdgeDestinationsToMap(map, nextNode, concurrentKeyList);

                    concurrentKeyList.remove();
                }
            } while (nextNode != null);


            return map;
        }

        private void addEdgeDestinationsToMap(HashMap<Node, BFSData> map, BFSSearchData activeNode, LinkedList<BFSSearchData> concurrentKeyList) {
            Iterator<Edge> iterator = activeNode.getNode().getEdges();
            if (iterator != null) {
                while (iterator.hasNext()) {
                    Edge e = iterator.next();
                    BFSData edgeDestNode = map.get(e.getDestNode());
                    if (edgeDestNode == null) {
                        concurrentKeyList.add(new BFSSearchData(e.getDestNode(), activeNode.getWorkingLevel() + 1));
                    }
                }
            }
        }
    }
// Verzeichnis aller Knoten des Graphen
    private HashMap<String, Node> nodeSet =
            new HashMap<String, Node>();

    public Graph() {
    }

    public Node addNode(String label)
            throws NodeAlreadyDefinedException {
        if (nodeSet.containsKey(label)) {
            throw new NodeAlreadyDefinedException();
        }
        Node n = new Node(label);
        nodeSet.put(label, n);
        return n;
    }

    public Node getNode(String label)
            throws NoSuchElementException {
        Node n = nodeSet.get(label);
        if (n == null) {
            throw new NoSuchElementException();
        }
        return n;
    }

    public void addEdge(String src, String dest) throws EdgeAlreadyDefinedException {
        Node srcNode = getNode(src);
        Node destNode = getNode(dest);
        srcNode.addEdge(new Edge(destNode, null));
    }

    public void addEdge(String src, String dest, int cost) throws EdgeAlreadyDefinedException {
        Node srcNode = getNode(src);
        Node destNode = getNode(dest);
        Edge newEdge = new Edge(destNode, cost);
        if (!edgeExists(srcNode, newEdge)) {
            srcNode.addEdge(newEdge);
        } else {
            throw new EdgeAlreadyDefinedException();
        }
        //edit franco: check if edge already exists
    }

    public boolean edgeExists(Node srcNode, Edge edge) {
        for (Edge activeEdge : srcNode.adjList) {
            if (activeEdge.getDestNode().getLabel().equals(edge.getDestNode().getLabel())) {
                return true;
            }
        }
        return false;
    }

    public int getNodeCount() {
        return nodeSet.keySet().size();
    }

    public int getEdgeCount() {
        int i = 0;
        for (Node n : nodeSet.values()) {
            i += n.adjList.size();
        }
        return i;
    }

    public String getNodeNames() {
        String output = "";
        for (String name : nodeSet.keySet()) {
            output += name + System.lineSeparator();
        }
        return output;
    }

    public String getEdgesFromNode(String src) {
        String output = "";
        for (Edge e : getNode(src).adjList) {
            if (e.getCostI() != null) {
                output += src + " " + e.getDestNode().getLabel() + e.getCost() + System.lineSeparator();
            } else {
                output += src + " " + e.getDestNode().getLabel() + System.lineSeparator();
            }
        }
        return output;
    }

    public ArrayList<Node> getShortestWay(String startS, String endS) throws NoSuchElementException {
        Node start = getNode(startS);
        Node end = getNode(endS);

        dijkstraGoGoGo(start);

        ArrayList<Node> list = new ArrayList<>();
        createWayBackRecursive(list, end);
        return list;
    }

    private void createWayBackRecursive(ArrayList<Node> list, Node activeNode) {
        if (activeNode.comesFrom == activeNode) {
            list.add(activeNode);
        } else {
            list.add(activeNode);
            createWayBackRecursive(list, activeNode.comesFrom);
        }
    }

    private void dijkstraGoGoGo(Node start) {
        cleanNodes();
        start.costToStartNode = 0;
        start.comesFrom = start;//comesFrom is used to check if it was visited
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(getNodeCount(), new NodeComperator());
        priorityQueue.add(start);
        dijkstraGoGoGoRecursive(priorityQueue);
    }

    private void dijkstraGoGoGoRecursive(PriorityQueue<Node> priorityQueue) {
        Node activeNode = priorityQueue.poll();
        if (activeNode != null) {
            if (!activeNode.adjList.isEmpty()) {
                for (Edge edge : activeNode.adjList) {
                    Node destNode = edge.dest;
                    int costToDestNode = activeNode.costToStartNode + edge.cost;
                    if (destNode.comesFrom == null || destNode.costToStartNode > costToDestNode) {
                        destNode.costToStartNode = costToDestNode;
                        destNode.comesFrom = activeNode;
                        priorityQueue.add(destNode);
                    }
                }
            }
            dijkstraGoGoGoRecursive(priorityQueue);
        }
    }

    private void cleanNodes() {
        for (Node node : nodeSet.values()) {
            node.costToStartNode = 0;
            node.comesFrom = null;
        }
    }
}
